package com.sjf.day02.huffmantree;

import org.jetbrains.annotations.NotNull;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 霍夫曼树 计算 wpl(带权路径最小值)
 *
 * @author <huangtang>
 * @since 2022/1/7 14:49
 **/
public class HuffmanTree {

    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        TreeNode huffmanTree = createHuffmanTree(arr);

        preOrder(huffmanTree);
    }

    public static void preOrder(TreeNode root){
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("树为空，不能遍历");
        }
    }

    //创建霍夫曼树
    public static TreeNode createHuffmanTree(int[] arr){
        List<TreeNode> nodeList = new ArrayList<>();
        for (int item : arr) {
            nodeList.add(new TreeNode(item)); //将数组的数构建成节点放进nodeList中
        }

        while(nodeList.size() > 1){
            //排序
            Collections.sort(nodeList);

            System.out.println(nodeList);

            //(1)取出根节点权值最小的两棵二叉树
            TreeNode leftNode = nodeList.get(0); //最小的
            TreeNode rightNode = nodeList.get(1);//次小的
            //(2)构建一颗新的二叉树
            TreeNode parent = new TreeNode(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            //(3)从nodeList中删除处理过的树
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);
            //(4)将parent加入到nodeList中
            nodeList.add(parent);
        }

        return nodeList.get(0); //返回树的头节点
    }
}


//节点,支持排序
class TreeNode  implements Comparable<TreeNode>{
    public int value;//节点权值
    public TreeNode left;//左子节点
    public TreeNode right;//右子节点

    public TreeNode(int value){
        this.value = value;
    }

    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(@NotNull TreeNode o) {
        return this.value - o.value;
    }
}
